package com.leetcode.www;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 *
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 * User:yxd
 * Date:2022-03-19
 * Time:0:01
 */
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class BFS429 {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null)return ret;
        Queue<Node> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();//一行里面所有的节点个数
            while(size-- != 0){//统计这一行所有的节点
                Node cur = queue.poll();//慢慢出队统计其子节点
                list.add(cur.val);
                for(Node n :cur.children){//此父节点的所有子节点全部入队
                    queue.offer(n);
                }

            }
            ret.add(new ArrayList<>(list));
            list.clear();//每一次都清空,统计下一行
        }
        return ret;
    }
}
